package com.yiwenup.struct._02_tree.base;


import com.yiwenup.printer.BinaryTreeInfo;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 二叉树接口
 **/
@SuppressWarnings("unchecked")
public class BinaryTree<E> implements BinaryTreeInfo {
    protected int size;
    protected Node<E> root;

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        root = null;
        size = 0;
    }

    /**
     * 先序遍历
     */
    public void preorderTraversal(Visitor<E> visitor) {
        preorderTraversal(root, visitor);
    }

    private void preorderTraversal(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor == null) {
            return;
        }
        System.out.println(node.element);
        preorderTraversal(node.left, visitor);
        preorderTraversal(node.right, visitor);
    }

    /**
     * 非递归实现前序遍历（使用栈保存一侧节点，待后续取出）
     */
    public void preorder(Visitor<E> visitor) {
        if (visitor == null || root == null) return;

        Node<E> node = this.root;
        Stack<Node<E>> stack = new Stack<>();

        while (true) {
            // 访问node节点
            if (node != null) {
                visitor.visit(node.element);
                if (node.right != null) stack.push(node.right);
                node = node.left;
            } else if (stack.isEmpty()) {
                return;
            } else {
                node = stack.pop();
            }
        }
    }

    /**
     * 非递归实现前序遍历
     */
    public void preorder2(Visitor<E> visitor) {
        if (visitor == null || root == null) return;

        Stack<Node<E>> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            Node<E> node = stack.pop();
            visitor.visit(node.element);
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }
    }

    /**
     * 中序遍历
     */
    public void inorderTraversal(Visitor<E> visitor) {
        inorderTraversal(root, visitor);
    }

    private void inorderTraversal(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor == null) return;
        inorderTraversal(node.left, visitor);
        System.out.println(node.element);
        inorderTraversal(node.right, visitor);
    }

    /**
     * 非递归实现中序遍历（使用栈保存中间节点，待后续取出）
     */
    public void inorder(Visitor<E> visitor) {
        if (visitor == null || root == null) return;

        Node<E> node = this.root;
        Stack<Node<E>> stack = new Stack<>();

        while (true) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else if (stack.isEmpty()) {
                break;
            } else {
                node = stack.pop();
                visitor.visit(node.element);
                node = node.right;
            }
        }
    }

    /**
     * 后序遍历
     */
    public void postorderTraversal(Visitor<E> visitor) {
        postorderTraversal(root, visitor);
    }

    public void postorderTraversal(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor == null) return;
        postorderTraversal(node.left, visitor);
        postorderTraversal(node.right, visitor);
        System.out.println(node.element);
    }

    /**
     * 非递归实现后序遍历（使用栈保存中间节点，待后续取出）
     */
    public void postorder(Visitor<E> visitor) {
        if (visitor == null || root == null) return;

        Stack<Node<E>> stack = new Stack<>();
        stack.push(root);

        // 记录上一次访问的节点
        Node<E> prev = null;
        while (!stack.isEmpty()) {
            Node<E> top = stack.peek();
            if (top.isLeaf() || (prev != null && prev.parent == top)) {
                prev = stack.pop();
                visitor.visit(prev.element);
            } else {
                if (top.right != null) stack.push(top.right);
                if (top.left != null) stack.push(top.left);
            }
        }
    }

    /**
     * 层序遍历
     */
    public void levelOrderTraversal(Visitor<E> visitor) {
        if (root == null || visitor == null) return;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
//            System.out.println(node.element);
            visitor.visit(node.element);

            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }

    /**
     * 查询前驱节点（中序遍历的前一个节点）
     *
     * @param node 当前节点
     * @return 当前节点的前驱节点
     */
    protected Node<E> predecessor(Node<E> node) {
        if (node == null) return null;

        // 前驱节点在左子树中 node.left.right.right.right....
        Node<E> pre = node.left;
        if (pre != null) {
            while (pre.right != null) {
                pre = pre.right;
            }
            return pre;
        }

        // 从父节点中寻找前驱节点
        while (node.parent != null && node == node.parent.left) {
            node = node.parent;
        }

        return node.parent;
    }

    /**
     * 查询后继节点（中序遍历的后一个节点）
     *
     * @param node 当前节点
     * @return 当前节点的后继节点
     */
    protected Node<E> successor(Node<E> node) {
        if (node == null) return null;

        // 前驱节点在左子树中 node.right.left.left.left....
        Node<E> pre = node.right;
        if (pre != null) {
            while (pre.left != null) {
                pre = pre.left;
            }
            return pre;
        }

        // 从父节点中寻找前驱节点
        while (node.parent != null && node == node.parent.right) {
            node = node.parent;
        }

        return node.parent;
    }

    /**
     * 二叉树的高度：递归方式
     */
    public int height() {
        return height(root);
    }

    private int height(Node<E> node) {
        if (node == null) return 0;
        return 1 + Math.max(height(node.left), height(node.right));
    }

    /**
     * 二叉树高度：迭代
     */
    public int height2() {
        if (root == null) return 0;

        int height = 0;
        int levelSize = 1;

        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            levelSize--;

            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);

            if (levelSize == 0) {
                levelSize = queue.size();
                height++;
            }
        }

        return height;
    }

    /**
     * 判断一棵树是否为完全二叉树
     */
    public boolean isComplete() {
        if (root == null) return false;

        Queue<Node<E>> queue = new LinkedList<>();

        queue.offer(root);

        boolean leaf = false;
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();

            if (leaf && !node.isLeaf()) return false;

            if (node.hasTwoChildren()) {
                queue.offer(node.left);
                queue.offer(node.right);
            } else if (node.left == null && node.right != null) {
                return false;
            } else {
                // 之后遍历的节点都是叶子节点
                leaf = true;
            }
        }

        return true;
    }

    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>) node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>) node).right;
    }

    @Override
    public Object string(Object node) {
        return node;
    }

    public static interface Visitor<E> {
        void visit(E element);
    }

    protected static class Node<E> {
        public E element;
        public Node<E> left;
        public Node<E> right;
        public Node<E> parent;

        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }

        public boolean isLeaf() {
            return left == null && right == null;
        }

        public boolean hasTwoChildren() {
            return left != null && right != null;
        }

        public boolean isLeftChild() {
            return parent != null && this == parent.left;
        }

        public boolean isRightChild() {
            return parent != null && this == parent.right;
        }

        public Node<E> sibling() {
            if (isLeftChild()) {
                return parent.right;
            }
            if (isRightChild()) {
                return parent.left;
            }
            return null;
        }
    }

    protected Node<E> createNode(E element, Node<E> parent) {
        return new Node<E>(element, parent);
    }
}
